/* dijkstra algorithm and MST(minimum spanning tree algorithm for a graph */
/* the dijkstra algorithm handles two circumstances: */
/*    1. directed acyclic graph can have negative edges */
/*    2. any graph without negative edges */
/* author:nemo(nemokingdom@gmail.com) */
/* date:Apr. 18th,2008 */


#include "graph.h"

extern int Post[MAXVERTEX]; 		/* in file explore.c */
extern EdgeInfo Info[MAXEDGE]; /* in file explore.c */

/* inject: refresh node's weight */
static void inject(PQueue *q, int node, int weight)
{
   q->q[node] = weight;
//   printf("inject: node %d with weight %d\n",node,weight);
}

/*eject: eject the smallest weight node */
static int eject(PQueue *q)
{
   int i;
   int min = 0;
   
   for(i = 1; i < q->len; i++)
      if(q->q[i] < q->q[min])
	 min = i;
//   printf("eject: eject node %d\n",min);
   return min;
}

static void initQueue(PQueue *q)
{
   int i;
   for(i = 0; i < q->len; i++)
      q->q[i] = 32768;
}

/* dagEject: q is unused,return node i with minimum Post[i] */
static int dagEject(PQueue *q)
{
   int i;
   int max = 0;
   for( i = 0; i < q->len; i++)
      if(q->q[i] > q->q[max])
	 max = i;
/*   printf("dagEject:%d\n",max);*/
   return max;
}

static void initDagQueue(PQueue *q)
{
   int i;
   for(i = 0; i < q->len; i++){
      q->q[i] = Post[i];
/*      printf("q[%d]: %d\n",i,q->q[i]);*/
   }
}

/* printmy: print the shortest routine to node i */
static void printmy(Graph *g,int *prev, int i)
{
   if(i == prev[i]){
      printf("*:%s ",g->vtab[i].name);
      return;
   }
   
   printmy(g,prev,prev[i]);
   printf("%s ",g->vtab[i].name);
}

/* dijkstra: dijkstra algorithm,using an array as a priority queue  */
/*           this function handles 2 graph:                         */
/*           1. graph without negative edges as showed below        */
/*           2. graph without cycles,this was by a 'dag:' notation  */
/*              you can safely replace last line with the annotations
		below                                               */
void dijkstra(Graph *g,char *start)
{
   int i,j,pos;
   int minmi;
   Edge *e;
   
   int Prev[g->v_num];
   int Weight[g->v_num];
   for( i = 0; i < g->v_num; i++){
      Prev[i] = -1;
      Weight[i] = 32768;
   }
   PQueue q;
   q.len = g->v_num;
   
   initQueue(&q);
/*dag: initDagQueue(&q);*/
   
   pos = locate(g,start);
   Prev[pos] = pos;
   Weight[pos] = 0;
   
   inject(&q,pos,0);
   /* dag:  */
      
   for(i = 0; i < g->v_num; i++){
      printf("get here\n");

      j = eject(&q);
      /*dag :j = dagEject(&q);*/
      
      for(e = g->vtab[j].edge; e != NULL; e = e->next){
	 if(Weight[e->vertex] > (Weight[j] + e->weight)){
	    Weight[e->vertex] = Weight[j] + e->weight;
	    
	    inject(&q,e->vertex,(q.q[j] + e->weight));
	    /* dag: */
	    
	    Prev[e->vertex] = j;
	 }
      }
      
      q.q[j] = 32768;
/* dag: q.q[j] = -1; */

   }

   for(i = 0; i < g->v_num; i++){
      if(Prev[i] == -1)
	 printf("can't reach\n");
      else{
	 printmy(g,Prev,i);
	 printf("with a total weight %d\n",Weight[i]);
      }
   }
}

/* ***************a partition line ***************** */

/* edgeCmp: using in sort Edgeinfo */
int edgeCmp(const void *e1, const void *e2)
{
   int i1 = ((const EdgeInfo *)e1)->weight;
   int i2 = ((const EdgeInfo *)e2)->weight;
   if(i1 < i2)
      return -1;
   if(i1 > i2)
      return 1;
   if(i1 == i2)
      return 0;
}

/* find: find which set it is, and compression the path to the set */
int find(int i, int *pi)
{
   if(pi[i] != i)
      pi[i] = find(pi[i], pi);
   return pi[i];
}

/* MST: minimum spanning tree algorithm*/
void MST(Graph *g)
{
   int i;
   int from,to,r1,r2;
   
   int pi[g->v_num];
   int rank[g->v_num];
   int prev[g->v_num];

   for(i = 0; i < g->v_num; i++)
      prev[i] = -1;
   
   for(i = 0; i < g->v_num; i++){
      rank[i] = 0;
      pi[i] = i;
   }
   qsort(Info, g->e_num, sizeof(EdgeInfo), edgeCmp);
   
   for(i = 0; i < g->e_num; i++){
      from = Info[i].from;
      to = Info[i].to;
      r1 = find(from, pi);
      r2 = find(to, pi);
      
      if(r1 != r2){
	 prev[to] = from;
	 if(rank[r1] > rank[r2])
	    pi[r2] = r1;
	 else
	    if(rank[r1] == rank[r2])
	       ++rank[r1];
	 pi[r1] = r2;
      }
   }
   
   for(i = 0; i < g->v_num; i++)
      printf("%s->%s\n",(prev[i]==-1)?"nil":g->vtab[prev[i]].name,g->vtab[i].name);
   
}

